package kyssion.leetcode.num201_250;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class code216_数字组合3 {

    public static void main(String[] args) {
        List<List<Integer>> listList = new code216_数字组合3().combinationSum3_2(3, 12);
        System.out.println();
    }

    /**
     * 简单暴利速度慢
     *
     * @param k
     * @param n
     * @return
     */
    public List<List<Integer>> combinationSum3_2(int k, int n) {
        use = new boolean[10];
        deque = new LinkedList<>();
        lists = new ArrayList<>();
        ans(k, n, 1);
        return lists;
    }

    private void ans(int k, int n, int start) {
        if (k == 0) {
            if (n == 0) {
                lists.add(new ArrayList<>(deque));
            }
            return;
        }
        while (start <= 9) {
            if (use[start]) {
                start++;
                continue;
            }
            deque.addLast(start);
            use[start] = true;
            ans(k - 1, n - start, start + 1);
            deque.removeLast();
            use[start] = false;
            start++;
        }
    }

    boolean[] use;
    Deque<Integer> deque;
    List<List<Integer>> lists;
    int[] max = new int[]{
            0, 9, 17, 24, 30, 35, 39, 42, 44, 45
    };

    /**
     * 分析题目找到关键点 不重复 三位数
     * 想到等差数列
     * 比如三位最大值是7+8+9 和目的值 7 进行对比
     * 依次针对最高位向下递减
     * 最终将会等到需要的值
     *
     * @param k
     * @param n
     * @return
     */
    public List<List<Integer>> combinationSum3(int k, int n) {
        use = new boolean[10];
        deque = new LinkedList<>();
        lists = new ArrayList<>();
        ansItem(k, n, 0);
        return lists;
    }

    private void ansItem(int k, int n, int start) {

        if (n > max[k]) {
            return;
        }

        if (k == 1) {
            deque.addLast(n);
            lists.add(new ArrayList<>(deque));
            deque.removeLast();
            return;
        }

        for (int a = start + 1; a <= 9; a++) {
            if (n - a < (((a << 1) + k) * (k - 1)) >> 1) {
                break;
            }
            deque.addLast(a);
            ansItem(k - 1, n - a, a);
            deque.removeLast();
        }
    }
}
